{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "某些时候我们知道遍历的结果，可以推得另一种遍历的结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def post(root, start, end, pre, ino):\n",
    "    # 终止条件：子树为空\n",
    "    if start > end:\n",
    "        return\n",
    "    \n",
    "    # 找到根节点在中序遍历中的位置\n",
    "    i = start\n",
    "    while i <= end and pre[root] != ino[i]:\n",
    "        i += 1\n",
    "\n",
    "    # 递归处理左子树\n",
    "    post(root + 1, start, i - 1, pre, ino)\n",
    "    # 递归处理右子树\n",
    "    post(root + 1 + i - start, i + 1, end, pre, ino)\n",
    "\n",
    "    # 输出当前根节点\n",
    "    print(pre[root], end=' ')\n",
    "\n",
    "# 示例输入\n",
    "pre = [1, 2, 4, 5, 3, 6, 7]  # 前序遍历\n",
    "ino = [4, 2, 5, 1, 6, 3, 7]  # 中序遍历\n",
    "\n",
    "# 调用函数，范围是整个树\n",
    "post(0, 0, len(ino) - 1, pre, ino)\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
